/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package pl.elka.gis.main.solvers;

import java.lang.Integer;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import pl.elka.gis.main.helper.EdgesHelper;
import pl.elka.gis.main.helper.GraphHelper;
import pl.elka.gis.main.helper.NodesHelper;
import pl.elka.gis.main.node.Edge;
import pl.elka.gis.main.node.Node;

/**
 *
 * @author Marcin
 */
public class MswSolver implements ISolver {

    @Override
    public Set<Edge> solve(Map<String, Set<String>> nodesMap) {
        SortedSet<Integer> C = new TreeSet<Integer>();
        HashMap<Node, Set<Edge>> graph = GraphHelper.bulidGraph(nodesMap);
        //KROK 1 ALGORYTMU
        SortedSet<Node> v1 = new TreeSet<Node>();
        for (Node v:graph.keySet()) {
            v1.add(v);
        }
        //KROK 3 ALGORYTMU
        for (Node v:v1) {
            //KROK 4 ALGORYTMU
            //zbiór kolorów dostępnych w węźle v
            SortedSet<Integer> Ctmp = new TreeSet<Integer>(C);
            //krawędzie do pokolorowania
            Set<Edge> Ev = graph.get(v);
            //krawędzie pokolorowane - potrzebne do usunięcia z Ev z powodu easy faultu Set'u
            Set<Edge> EvToColor = new HashSet<Edge>();
            //użyte kolory w krawędziach węzła v
            SortedSet<Integer> Cv = new TreeSet<Integer>();
            for(Edge e:Ev) {
                if (e.isColored()) {
                    Cv.add(e.getColor());
                } else {
                    EvToColor.add(e);
                }
            }
            //KROK 5 ALGORYTMU
            //pobierz krawędź
            for(Edge e:EvToColor) {
                //użyte kolory w krawędziach węzła v usuń ze zbioru dostępnych kolorów
                Ctmp.removeAll(Cv);
                Node trg;
                //węzeł v jest oznaczony w krawędzi jako bliższy
                //bierzemy kolory z krawędzi dalszego węzła
                if (v.equals(e.getnFrom())) {
                    trg = e.getnTo();
                }
                //węzeł v jest oznaczony w krawędzi jako dalszy
                //bierzemy kolory z krawędzi bliższego węzła
                else {
                    trg = e.getnFrom();
                }
                //zbiór kolorów dostępnych dla krawędzi e
                //(wszystkie kolory minus użyte w krawędziach węzła v;
                //należy od tego odjąć kolory użyte w dalszym węźle)
                SortedSet<Integer> Ctrgtmp = new TreeSet<Integer>(Ctmp);
                //użyte kolory w krawędziach dalszego węzła
                SortedSet<Integer> Ctrg = new TreeSet<Integer>();
                for(Edge trgEdge:graph.get(trg)) {
                    if (trgEdge.isColored())
                        Ctrg.add(trgEdge.getColor());
                }
                //użyte kolory w krawędziach dalszego węzła usuń ze zbioru dostępnych kolorów
                Ctrgtmp.removeAll(Ctrg);
                //wybierz najtańszy kolor
                Integer cheapestColor;                
                if (Ctrgtmp.isEmpty()) {
                    //nie ma dostępnych kolorów, trzeba dodać kolor
                    if (C.isEmpty())
                        //w ogóle nie ma kolorów! jako najtańszy przyjmujemy pierwszy kolor
                        cheapestColor = new Integer(1);                    
                    else
                        //jako najtańszy przyjmujemy ostatni kolor plus 1
                        cheapestColor = new Integer(C.last().intValue()+1);
                    //dodajemy kolor do ogólnej palety
                    C.add(cheapestColor);
                }
                //jest dostępny kolor
                else {
                    cheapestColor = Ctrgtmp.first();
                }
                //dodaje kolor do użytych w węźle
                Cv.add(cheapestColor);
                //w końcu koloruję krawędź
                e.setColor(cheapestColor);
                //
            }
        }
        Set<Edge> returnEdges = new HashSet<Edge>();
        for (Collection c:graph.values()) {
            returnEdges.addAll(c);
        }
        return returnEdges;
    }

}
